public class BinarySearchTree {
    public class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node root;

    public boolean jc(int val) {
        Node cur = root;
        while (cur != null) {
            if (val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            } else {
                return true;
            }
        }
        return false;
    }

    public void cha(int val) {
        Node cut = new Node(val);
        if (root == null) {
            root = cut;
        }
        Node cur = root;
        Node parter = null;
        while (cur != null) {
            if (cut.val > cur.val) {
                parter = cur;
                cur = cur.right;
            } else if (val == cur.val) {
                return;
            } else {
                parter = cur;
                cur = cur.left;
            }
        }
        if (parter.val < cut.val) {//不能使用parter.left(right)！=null去判两边都是null直接后续插入不了
            parter.right = cut;
        } else {
            parter.left = cut;
        }
    }

    public void remove(int val) {
        Node cut = new Node(val);
        Node cur = root;
        Node parter = null;
        while (cur != null) {
            if (cut.val > cur.val) {
                parter = cur;
                cur = cur.right;
            } else if (val < cur.val) {
                parter = cur;
                cur = cur.left;
            } else {
                delet(parter,cur);
                return;
            }
        }
    }
    public void delet(Node parter,Node cur){
      if(cur.right==null){
          if(cur==root){
              root=root.left;
          }
          if(parter.left==cur){
              parter.left=cur.left;
          }
          if(parter.right==cur){
              parter.right=cur.left;
          }

      }else if(cur.left==null){
          if(cur==root){
              root=root.right;
          }
          if(parter.left==cur){
              parter.left=cur.right;
          }
          if(parter.right==cur){
              parter.right=cur.right;
          }
      }else {
//          Node target=cur.right;
//          Node ptarget=cur;
//          Node pptarget=null;
//          while (target!=null){
//              pptarget=ptarget;
//              parter=target;
//              target=target.left;
//          }
//          cur.val=parter.val;
//          if(pptarget.left==parter){
//              pptarget.left=parter.right;
//          }
//          else{
//              pptarget.right=parter.right;
//          }
          Node target=cur.right;
          Node ptarget=cur;
          while (target.left!=null){
              ptarget=target;
              target=target.left;
          }
          cur.val=target.val;
          if(ptarget.left==target){
              ptarget.left=target.right;
          }else {
              ptarget.right=target.right;
          }
      }

    }
}
